This invention relates generally to decoding, such as low density parity check (LDPC) decoding.
Present day storage systems employ a number of different techniques to eliminate errors that may occur during a data readback process. Every block that is read is decoded “on-the-fly” in a single read attempt, and if unsuccessful, after some number of rereads. If the rereads are unsuccessful, the block is then subject to a data recovery procedure. Typically, the “on-the-fly” decoding and the rereads are performed by a hardware decoder. When a reread operation is performed, the operating conditions are varied slightly, for example, by offsetting a transducer from a center of a track, to obtain a slightly different waveform. The reread operations repeat until the erroneous data are corrected or a predetermined number of reread operations has been performed, at which point the reread process may be terminated and a firmware-implemented data recovery procedure takes over.
It is possible to perform rereads and data recovery procedures to improve performance as long as the throughput of the storage system is not unacceptably degraded. Preferably, for example, a storage system is designed to ensure that reread and data recovery procedures do not slow the throughput by more than a predetermined throughput specification, e.g., 0.5%. Additionally, the system can ensure compliance with a reliability specification, for example, a reliability specification of 10−12, which specifies that no more than one block out of 1012 blocks read should fail to return correct data after a prescribed number of rereads and data recovery procedures are exercised. At present there are very clear boundaries between the “on-the-fly”, reread, and firmware-implemented data recovery modes. What matters most, however, is that the two fundamental specifications of throughput and reliability, are satisfied.
Iterative decoding is a class of powerful detector/decoder architectures in which the detector provides symbol reliability values to the decoder and the decoder in turn provides reliability values back to the detector. One example of such an iterative system applies the so-called Low Density Parity Check (LDPC) code. When many iterations between the detector and decoder are allowed, it is possible to achieve a significant performance gain (e.g., approximately 3 dBs for 100 iterations) relative to other architectures such as the Reed-Solomon (RS) decoders. Unfortunately, implementing just a single iteration in hardware is a major challenge in terms of hardware complexity, and implementing many more iterations can be extremely costly. On the other hand, when only a few iterations in hardware are allowed, much of the performance improvement is lost, e.g., a 3 dB gain for 100 iterations may be reduced to a single dB when just two iterations are performed.
Containing the complexity and implementation size of an LDPC decoder is a major concern. At present, there exist multiple algorithms that simplify the decoder complexity with small signal-to-noise-ratio (SNR) performance loss. However, these simplifying algorithms degrade a burst erasure capability of the LDPC code/decoder. There remains a need, therefore, for an efficient LDPC decoder that both simplifies the decoder complexity and provides for sufficient burst erasure capability.